
import java.util.LinkedList;

public class memory {

    private int size;//内存大小
    private static final int MIN_SIZE =3;//最小剩余分区大小
    private LinkedList<Partition> mpartition;//内存分区
    private int location;//上次分配的空闲区位置

    class Partition{//分区节点类
        private int size;//分区大小
        private int head;//分区始址
        private boolean Free;//空闲状态
        //有参构造器
        public Partition(int head, int size) {
            this.head = head;
            this.size = size;
            this.Free = true;
        }
    }

    public memory(int size) {
        this.size = size;
        this.location = 0;
        this.mpartition = new LinkedList<>();
        mpartition.add(new Partition(0, size));
    }

    //首次适应算法
    //size 指定需要分配的大小
    void FristFit(int size){
        //遍历分区链表
        for (location = 0; location < mpartition.size(); location++){//每次从链首开始查找
            Partition temp =mpartition.get(location);
            if (temp.Free && (temp.size > size)){//找到可用空闲分区且大小足够
                Distribute(size, location, temp);
                return;
            }
        }
        //遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }

    //执行分配函数,size 申请大小,location 当前可用分区位置,temp 可用空闲区
    private void Distribute(int size, int location, Partition temp) {
        //如果分割后分区剩余大小过小（MIN_SIZE）则将分区全部分配，否则分割为两个分区
        if (temp.size - size <= MIN_SIZE){
            temp.Free = false;
        } else {
            Partition split = new Partition(temp.head + size, temp.size - size);
            mpartition.add(location + 1, split);
            temp.size = size;
            temp.Free = false;
        }
        System.out.println("成功分配 " + size + "KB 的内存!");
    }

    //内存回收,id 指定要回收的分区号
    public void collection(int id){
        if (id >= mpartition.size()){
            System.out.println("没有此分区号!");
            return;
        }
        Partition temp = mpartition.get(id);
        int size = temp.size;
        if (temp.Free) {
            System.out.println("分区未被分配, 无需回收");
            return;
        }
        //如果回收分区不是尾分区且后一个分区为空闲, 则与后一个分区合并（上不邻下邻或者上下都邻）
        if (id < mpartition.size() - 1 && mpartition.get(id + 1).Free){
            Partition next = mpartition.get(id + 1);
            temp.size += next.size;
            mpartition.remove(next);
        }
        //如果回收分区不是首分区且前一个分区为空闲, 则与前一个分区合并（上邻下不邻或者上下都邻）
        if (id > 0 && mpartition.get(id - 1).Free){
            Partition previous = mpartition.get(id - 1);
            previous.size += temp.size;
            mpartition.remove(id);
            id--;
        }
        mpartition.get(id).Free = true;
        System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
    }

    //展示内存分区状况
    public void showmpartition(){
        System.out.println("*****************************************");
        System.out.println("分区编号   分区始址   分区大小   空闲状态");
        for (int i = 0; i < mpartition.size(); i++){
            Partition temp = mpartition.get(i);
            System.out.println(i + "\t\t\t" + temp.head + "\t\t  " +
                    temp.size + "\t\t" + temp.Free);
        }
        System.out.println("*****************************************");
    }
}


